package demo6;

import java.util.HashMap;
import java.util.Map.Entry;


public class TestDemo {

    static class Info{
        public int[] coins;
        public int[] zhang;
        public Info(int[] coins,int[] zhang){
            this.coins = coins;
            this.zhang = zhang;
        }
    }

    public static Info getInfo(int[] arr){
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int val : arr){
            map.put(val,map.getOrDefault(val,0)+1);
        }
        int N = arr.length;
        int[] coins = new int[N];
        int[] zhang = new int[N];
        int index = 0;
        for(Entry<Integer, Integer> entry : map.entrySet()){
            coins[index] = entry.getKey();
            zhang[index++] = entry.getValue();
        }
        return new Info(coins,zhang);
    }

    public static int coinsWays1(int[] arr,int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        return process(info.coins,info.zhang,0,aim);
    }

    public static int process(int[] coins,int[] zhang,int index,int rest){
        if(index == coins.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for(int zhangs =0;zhangs*coins[index]<=rest && zhangs<=zhang[index];zhangs++){
            ways += process(coins,zhang,index+1,rest-zhangs*coins[index]);
        }
        return ways;
    }

    public static int waysDp(int[] arr,int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhang = info.zhang;
        int N = info.coins.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1;
        for(int index = N-1;index>=0;--index){
            for(int rest =0;rest<=aim;++rest){
                int ways = 0;
                for(int zhangs =0;zhangs*coins[index]<=rest && zhangs<=zhang[index];zhangs++){
                    ways += process(coins,zhang,index+1,rest-zhangs*coins[index]);
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }


    public static int waysDp1(int[] arr,int aim){
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhang = info.zhang;
        int N = info.coins.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1;
        for(int index = N-1;index>=0;--index){
            for(int rest =0;rest<=aim;++rest){
                dp[index][rest] += dp[index+1][rest];
                if(rest-coins[index]>=0){
                    dp[index][rest] += dp[index][rest-coins[index]];
                }
                if(rest -((zhang[index]+1)*coins[index])>=0){
                    dp[index][rest] -= dp[index+1][rest - ((zhang[index]+1)*coins[index])];
                }
            }
        }
        return dp[0][aim];
    }

    public static int dp2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhangs = info.zhang;
        int N = coins.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest - coins[index] >= 0) {
                    dp[index][rest] += dp[index][rest - coins[index]];
                }
                if (rest - coins[index] * (zhangs[index] + 1) >= 0) {
                    dp[index][rest] -= dp[index + 1][rest - coins[index] * (zhangs[index] + 1)];
                }
            }
        }
        return dp[0][aim];
    }

    // 为了测试
    public static int[] randomArray(int maxLen, int maxValue) {
        int N = (int) (Math.random() * maxLen);
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = (int) (Math.random() * maxValue) + 1;
        }
        return arr;
    }

    // 为了测试
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // 为了测试
    public static void main(String[] args) {
        int maxLen = 10;
        int maxValue = 20;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int aim = (int) (Math.random() * maxValue);
            int ans1 = waysDp1(arr, aim);
            int ans3 = dp2(arr, aim);
            if (ans1 != ans3) {
                System.out.println("Oops!");
                printArray(arr);
                System.out.println(aim);
                System.out.println(ans1);
                System.out.println(ans3);
                break;
            }
        }
        System.out.println("测试结束");
    }

}
